/* Peter Banda, Daniel Cristofani, Dominic Tippabattuni                     */
/* 975530978    971012079          958842138                                */
/* VMM_Sim Implementation (assignment 5)                                    */
/* CS 538, Portland State University, Fall 2010                             */
/* Turned in November 18, 2010                                              */

/* vmm.c contains the bulk of the vmm simulator.                            */

#include "vmm.h"

struct PageTableInfo pdbr[NO_PD_ENTRIES];	//The simulated VMM state.

// allocate a new page table
struct UserPageInfo *makePageTable(void)
{
    struct UserPageInfo *returnValue, *i;
    if (!(returnValue = malloc((sizeof(struct UserPageInfo)) * NO_PT_ENTRIES))) {
	 error("The simulator has run out of memory. Please increase its memory allocation or run it without -t.");
    }
    for (i = returnValue; i < returnValue + NO_PT_ENTRIES; i++) {
	i->presentBit = 0;
	i->accessedBit = 0;
	i->existsBit = 0;
	i->dirtyBit = 0;
    }
    return returnValue;
}

// retrieve an entry from the page directory.
struct PageTableInfo *getPageTableInfo(int ptIndex)
{
    return pdbr + ptIndex;
}

// retrieve an entry from a page table
struct UserPageInfo *getUserPageInfo(struct PageTableInfo *pti,
				     int upIndex)
{
    return pti->pageTable + upIndex;
}

// returns an integer made from the most significant 10 bits of vAddress.
int getPTIndex(unsigned long vAddress)
{
    return (vAddress >> 22);
}

// returns an integer made from the next 10 bits (11th to 21st) of vAddress.
int getUPIndex(unsigned long vAddress)
{
    return (vAddress >> 12) & 1023;
}

// if page table's exists bit is 0, call recordPTExists. set exists bit to 1.
void setPTExistsBit(struct PageTableInfo *pti)
{
    if (!pti->existsBit) {
	recordPTExists();
    }
    pti->existsBit = true;
}

// if user page's exists bit is 0, call recordUPExists and set exists bit to 1.
void setUPExistsBit(struct UserPageInfo *upi)
{
    if (!upi->existsBit) {
	recordUPExists();
    }
    upi->existsBit = true;
}

// if page table's present bit is 0, call recordPTResident. set present bit to 1.
void setPTPresentBit(struct PageTableInfo *pti)
{
    if (!pti->presentBit) {
	recordPTResident();
    }
    pti->presentBit = true;
}

// if user page's present bit is 0, call recordUPResident and set present bit to 1.
void setUPPresentBit(struct UserPageInfo *upi)
{
    if (!upi->presentBit) {
	recordUPResident();
    }
    upi->presentBit = true;
}

// if page table's present bit is 1, call recordPTNonResident. set present bit to 0.
void clearPTPresentBit(struct PageTableInfo *pti)
{
    if (pti->presentBit) {
	recordPTNonResident();
    }
    pti->presentBit = false;
}

// if user page's present bit is 1, call recordUPNonResident and set present bit to 0.
void clearUPPresentBit(struct UserPageInfo *upi)
{
    if (upi->presentBit) {
	recordUPNonResident();
    }
    upi->presentBit = false;
}

//  record swapping in page table from disk, update entry
void swapInPT(struct PageTableInfo *pti)
{
    setPTPresentBit(pti);
    recordSwapIn();
}

// record swapping in user page from disk, update entry
void swapInUP(struct UserPageInfo *upi)
{
    setUPPresentBit(upi);
    recordSwapIn();
}

// if page table's present or exists bit is 0, then ERROR is produced. Function recordSwapOut() is called. Update entry in page directory (page table info).
void swapOutPT(struct PageTableInfo *pti)
{
    if (!pti->existsBit || !pti->presentBit) {
	error
	    ("Page table that need to be swapped out has 0 present or exists bit.");
    } else {
	clearPTPresentBit(pti);
	recordSwapOut();
    }
}

//  if user page's exists bit is 0, then ERROR is produced. Dirty bit is cleared and recordSwapOut() is called. Update entry in page table (user page info).
void swapOutUP(struct UserPageInfo *upi)
{
    if (!upi->existsBit || !upi->presentBit) {
	error
	    ("User page that need to be swapped out has 0 present or exists bit.");
    } else {
	upi->dirtyBit=0;
	clearUPPresentBit(upi);
	recordSwapOut();
    }
}

// searches for a clean user page not recently accessed. search starts at a  location within a  page table.
struct UserPageInfo *findUnaccessedClean(void)
{
    int i, j;
    struct UserPageInfo *upi;
    for (i = 0; i < NO_PD_ENTRIES; i++) {
	if (pdbr[i].presentBit) {
	    for (j = 0; j < NO_PT_ENTRIES; j++) {
		upi = getUserPageInfo(getPageTableInfo(i), j);
		if (upi->presentBit && !upi->accessedBit && !upi->dirtyBit) {
		    return upi;
		}
	    }
	}
    }
    return NULL;
}

// searches for any user page not recently accessed.
struct UserPageInfo *findUnaccessedDirty(void)
{
    int i, j;
    struct UserPageInfo *upi;
    for (i = 0; i < NO_PD_ENTRIES; i++) {
	if (pdbr[i].presentBit) {
	    for (j = 0; j < NO_PT_ENTRIES; j++) {
		upi = getUserPageInfo(getPageTableInfo(i), j);
		if (upi->presentBit && !upi->accessedBit) {
		    return upi;
		}
	    }
	}
    }
    return NULL;
}

// searches for a page table not recently accessed.
struct PageTableInfo *findUnaccessedPT(void)
{
    int i;
    for (i = 0; i < NO_PT_ENTRIES; i++) {
	if (pdbr[i].presentBit && !pdbr[i].accessedBit) {
	    return pdbr + i;
	}
    }
    return NULL;
}

// searches for any clean user page.
struct UserPageInfo *findAccessedClean(void)
{
    int i, j;
    struct UserPageInfo *upi;
    for (i = 0; i < NO_PD_ENTRIES; i++) {
	if (pdbr[i].presentBit) {
	    for (j = 0; j < NO_PT_ENTRIES; j++) {
		upi = getUserPageInfo(getPageTableInfo(i), j);
		if (upi->presentBit && !upi->dirtyBit) {
		    return upi;
		}
	    }
	}
    }
    return NULL;
}

// searches for any user page.
struct UserPageInfo *findAccessedDirty(void)
{
    int i, j;
    struct UserPageInfo *upi;
    for (i = 0; i < NO_PD_ENTRIES; i++) {
	if (pdbr[i].presentBit) {
	    for (j = 0; j < NO_PT_ENTRIES; j++) {
		upi = getUserPageInfo(getPageTableInfo(i), j);
		if (upi->presentBit) {
		    return upi;
		}
	    }
	}
    }
    return NULL;
}

// searches for any page table.
struct PageTableInfo *findAccessedPT(void)
{
    int i;
    for (i = 0; i < NO_PT_ENTRIES; i++) {
	if (pdbr[i].presentBit) {
	    return pdbr + i;
	}
    }
    return NULL;
}

// checks if there is any empty page frame.
bool findEmptyPageFrame(void)
{
    struct Stats stats = getStats();
    return ((1 + stats.residentPageTableCount +
	stats.residentUserPageCount) < noOfPageFrames);
}

// finds a page frame, freeing one up by swapping something out if necessary.
// we don't actually need to track the page frames, only their number.
void findPageFrame(void)
{
    struct UserPageInfo *upi = NULL;
    struct PageTableInfo *pti = NULL;
    if (findEmptyPageFrame()) { //do nothing!
    } else if ((upi = findUnaccessedClean()) != NULL) {
	clearUPPresentBit(upi);
	recordReplacement();
    } else if ((upi = findUnaccessedDirty()) != NULL) {
	swapOutUP(upi);
    } else if ((pti = findUnaccessedPT()) != NULL) {
	swapOutPT(pti);
    } else if ((upi = findAccessedClean()) != NULL) {
	clearUPPresentBit(upi);
	recordReplacement();
    } else if ((upi = findAccessedDirty()) != NULL) {
	swapOutUP(upi);
    } else if ((pti = findAccessedPT()) != NULL) {
	swapOutPT(pti);
    } else {
	error("No accessed or unaccessed page frames!");
    }
}

// create, or swap in, a page table.
void getPT(struct PageTableInfo *pti)
{
    findPageFrame();
    if (pti->existsBit==1) {
	swapInPT(pti);
    } else {
	pti->pageTable=makePageTable();
	setPTExistsBit(pti);
    }
    setPTPresentBit(pti);
}

// create, or swap in, a user page.
void getUP(struct UserPageInfo *upi)
{
    findPageFrame();
    if (upi->existsBit==1) {
	swapInUP(upi);
    } else {
	setUPExistsBit(upi);
    }
    setUPPresentBit(upi);
}

// this function just encapsulates the huge chunk of functionality that is
// common to read() and write() as defined in the spec.
struct UserPageInfo *access(unsigned long vAddress)
{
    int ptIndex, upIndex;
    struct PageTableInfo *pti;
    struct UserPageInfo *upi;
    ptIndex = getPTIndex(vAddress);
    pti = getPageTableInfo(ptIndex);
    if (pti->presentBit==0) {
	getPT(pti);
    }
    pti->accessedBit=1;
    upIndex = getUPIndex(vAddress);
    upi = getUserPageInfo(pti, upIndex);
    if (upi->presentBit==0) {
	getUP(upi);
    }
    upi->accessedBit=1;
    return upi;
}

// prints the state of all active page tables, for the -l command.
void printOverallVMMState(void){
	int i;
	struct PageTableInfo *pti;
	struct UserPageInfo *upi;
	if (lFlag){
		for(i=0;i<NO_PD_ENTRIES;i++){
			pti=getPageTableInfo(i);
			if(pti->existsBit==1){
				printf("Page table 0x%3x: exists, %s,%s recently accessed. Entries:\n",i,pti->presentBit?"resident":"swapped out",pti->accessedBit?"":" not");
				printf("    Key: uppercase letters represent 1 bits, lowercase letters represent 0 bits.\n");
				printf("    Each entry in the page table has four bits: (P)resent, (E)xists, (A)ccessed recently, (D)irty.\n");
				for(upi=pti->pageTable;upi<pti->pageTable+NO_PT_ENTRIES;upi++){
					printf("%c%c%c%c%c",upi->presentBit?'P':'p',upi->existsBit?'E':'e',upi->accessedBit?'A':'a',upi->dirtyBit?'D':'d',((upi-pti->pageTable)&15)==15?'\n':' ');
				}
				printf("\n");
			}
		}
		for(i=0;i<79;i++){
			printf("-");
		}
		printf("\n\n");
	}
}

// Clear all "accessed" bits from resident tables and pages, for the LRU_approximation.
void clearAccessedBits(void)
{
    int i, j;
    struct UserPageInfo *upi;
    for (i = 0; i < NO_PD_ENTRIES; i++) {
	if (pdbr[i].presentBit) {
            pdbr[i].accessedBit=0;
	    for (j = 0; j < NO_PT_ENTRIES; j++) {
		upi = getUserPageInfo(getPageTableInfo(i), j);
		if (upi->presentBit) {
		    upi->accessedBit=0;
		}
	    }
	}
    }
}

// Simulate a read command.
void read(unsigned long vAddress)
{
    access(vAddress);
    recordRead();
    printOverallVMMState();
	if (getTotalAccesses()%ACCESS_CLEAR_PERIOD==0){
		clearAccessedBits();
	}
}

// Simulate a write command.
void write(unsigned long vAddress)
{
    struct UserPageInfo *upi = access(vAddress);
    upi->dirtyBit=1;
    recordWrite();
    printOverallVMMState();
	if (getTotalAccesses()%ACCESS_CLEAR_PERIOD==0){
		clearAccessedBits();
	}
}

